package uestc.lj.midPromotion.tree;

/**
 * @Author:Crazlee
 * @Date:2021/12/4
 */
public class Code03_CompleteTreeNodeNumber {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static int nodeNumber(Node root) {
		if (root == null) {
			return 0;
		}
		return bs(root, 1, mostLeftLevel(root, 1));
	}

	private static int bs(Node root, int level, int h) {
		if (level == h) {
			return 1;
		}
		if (mostLeftLevel(root.right, level + 1) == h) {
			// 左树是满的
			return (1 << (h - level)) + bs(root.right, level + 1, h);
		} else {
			// 右树是满的
			return (1 << (h - level - 1)) + bs(root.left, level + 1, h);
		}
	}

	/**
	 * 求树的深度
	 *
	 * @param node  当前节点
	 * @param level 当前节点所在的层次
	 * @return 深度
	 */
	private static int mostLeftLevel(Node node, int level) {
		while (node != null) {
			node = node.left;
			level++;
		}
		return level - 1;
	}

	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		System.out.println(nodeNumber(head));

	}

}
